1. Technical Field
The present invention relates to congestion control of data networks, and more particularly, relates to a congestion avoidance mechanism for packet-switched networks, especially wireless or mobile networks.
2. Related Art
A data network is a collection of network devices, or nodes interconnected by point-to-point links. Communication links may be wired (i.e., optical fiber) or wireless (i.e., infrared or radio-frequency) for supporting a number of logical point-to-point channels. Each channel may be a bi-directional communication path for allowing commands and message data to flow between two network devices or nodes within the data network. Network devices or nodes may be categorized as either end systems or routers, which are also known as intermediate systems or communication gateways. End systems may include PCs, workstations, mainframes, file servers, storage devices and other types of computers. Router may include a number of communication links for forwarding data arriving over one link onto another link for transmission to an end system or another router.
Generally, end systems both send data to other end stations on the data network and receive data sent by other end systems on the data network. When an end system serves as a sender of data, it is referred to as a source for that data; whereas, when such an end station serves as a receiver of data, it is referred to as a destination for the data. Typically, end systems may act as both sources and destinations depending upon whether they are sending or receiving data. When acting as a source, the end system sends data in the form of messages over a communication link to a router for transferring the messages to an end system or another router.
Each message may comprise a sequence of information bits. Typically, however, the messages sent over the data network are not sent as a continuous, uninterrupted stream of bits. Rather, they are divided up into smaller blocks of information called packets, which are then transmitted individually. Each packet has a predetermined maximum length. In addition to a data field which contains the data to be transferred, a packet also includes a header field which contains control information such as format, identifiers which indicate what portion of the message is contained in the packet, the source of the packet and the intended destination of the packet. When the packets which together contain a message reach the destination, the destination processes them by assembling their data fields into proper order to reconstruct the full message.
One important design objective in data networks is controlling the flow of packets so that such packets may not be transmitted at a faster rate than they can be processed by the routers through which the packets may pass or by the destinations. Even in the simplest data network consisting of two end systems interconnected by a router, for example, the source may flood the destination if it transmits packets faster than they can be processed by the destination. In more complicated networks consisting of many end systems, numerous routers and alternative communication paths between the end systems, the likelihood of problems from excess communication traffic is significantly greater. This becomes especially true as the number of active end systems on the network increases and if communication speeds of the equipment within the network are mismatched. A mismatch may exist if, for example, a router cannot transfer packets as fast as they are being sent to it by the source. A mismatch may also exist between the speed at which the link can transmit packets, namely the link speed, and the rate at which the router can transfer packets. Predictably, as the complexity of the network increases, achieving an acceptable traffic control also becomes more difficult.
On most networks, including TCP/IP packet-switched networks in which Transmission Control Protocol (TCP) [RFC 793, September 1981] may be implemented to ensure high-speed and high-quality data transfer in the Internet, at least two basic mechanisms are normally used for dealing with excess traffic arriving at a destination. One mechanism involves the use of buffers and the other involves flow control. In buffered systems, both the routers and the end systems (i.e., source node and destination node) are provided with buffer memory to handle data overloads. Arriving traffic which exceeds the processing rate of the device is temporarily stored in the buffer memory until the device can process it. Buffers offer a satisfactory solution to excess traffic problems only if the overload is transitory. If the overload persists for too long, the buffers may become full after which the additional packets are rejected or destroyed.
The other mechanism, generally referred to as flow control, deals with the allocation of resources at the destination, such as memory and processing. Generally, in accordance with flow control, the destination sets a limit on the transmission rate at which each source sending data to the destination may transmit that data. The sources and the destinations coordinate the transfer of data by an exchange of messages containing requests and acknowledgments. Before the source starts sending packets, it will send a request to the destination seeking permission to begin transmission. In response to the request, the destination sends a message containing an identification of the number of packets the source may dispatch toward the destination without further authorization. This number is commonly referred to as the window size. The source then proceeds to transmit the authorized number of packets toward the destination and waits for the destination to verify their receipt. After the destination successfully receives a packet, it sends a message back to the source containing an acknowledgment indicating the successful receipt of the packet and, in some cases, authorizing the source to send another packet. In this way, the number of packets on the network traveling from the source toward the destination will never be more than the authorized window size.
Neither of these mechanisms, however, satisfactorily deals with the distribution of traffic within the network. Even with these mechanisms in place, on a busy network it is likely that many sources will simultaneously send traffic over the network to more than one destination. If too much of this traffic converges on a single router in too short a time, the limited buffer capacity of the router will be unable to cope with the volume and the router or communication gateway will reject or destroy the packets. When this happens, the network is said to be congested.
Then the network is congested, network performance degrades significantly. The affected sources have to retransmit the lost or rejected packets. Re-transmissions, however, necessarily use network resources such as buffer storage, processing time and link bandwidth to handle old traffic thereby leaving fewer resources for handling those portions of the messages still waiting to be transmitted for the first time. When that occurs, network delays increase drastically and network throughput drops. Indeed, since some network resources are being dedicated to handling re-transmissions at a time when the network is already experiencing a heavy load, there is a substantial risk of the congestion spreading and locking up the entire network.
A variety of alternative approaches exist for dealing with network congestion. Generally, the approaches fall into two categories. One category involves placing limitations on the amount of traffic which will be permitted on the network at any given time. Examples include the preallocation of buffers at the routers to ensure that memory is available to store arriving packets until they can be forwarded. The other category involves methods of limiting the spread of congestion once it occurs and then extricating the network from its congested state. The second category of approaches for dealing with network congestion is commonly referred to as congestion control. Congestion control typically involves feedback which signals the onset of congestion overflow and instructs end systems to decrease the rate at which they initiate transmission of packets.
Currently, there are several schemes, including the recent proposed use of Explicit Congestion Notification (ECN) mechanisms in the TCP/IP networks to avoid unnecessary delay for packets from low-bandwidth delay-sensitive TCP connections. Such proposals are described, for example, in Floyd, S., xe2x80x9cTCP and Explicit Congestion Notification,xe2x80x9d ACM Computer Communication Review, V. 24 N. 5, October 1994, p. 10-23; Ramakrishnan, K. K., and Floyd, S., xe2x80x9cA Proposal to add Explicit Congestion Notification (ECN) to IP,xe2x80x9d RFC 2481, January 1999; Floyd, Black, and Ramakrishnan, xe2x80x9cIPsec Interactions with ECN,xe2x80x9d internet-draft draft-ietf-ipsec-ecn-02.txt, October, 1999; Ramakrishnan, Floyd, and Davie, xe2x80x9cProposal to Incorporate ECN in MPLS,xe2x80x9d internet-draft draft-mpls-ecn-00.txt, June, 1999; Jamal Hadi Salim and Uvaiz Ahmed, Performance Evaluation of Explicit Congestion Notification (ECN) in IP Networks, draft-hadi-jhsua-ecnperf-01.txt, March 2000; Uvaiz Ahmed and Jamal Hadi Salim, xe2x80x9cPerformance Evaluation of Explicit Congestion Notification (ECN) in IP Networks,xe2x80x9d December 1999; Chris Chen, Hariharan Krishnan, Steven Leung, Nelson Tang, xe2x80x9cImplementing Explicit Congestion Notification (ECN) in TCP for IPv6,xe2x80x9d report for CS 217, December 1997; Prasad Bagal, Shivkumar Kalyanaraman, Bob Packer, xe2x80x9cComparative study of RED, ECN and TCP Rate Control,xe2x80x9d Technical Report, March 1999.
Generally, Explicit Congestion Notification (ECN) mechanisms are installed in intermediate nodes, such as routers or communication gateways, to detect and notify the incipient congestion in the TCI/IP networks. The router may monitor the average of queue size. When the average of queue size exceeds a designated threshold previously defined, the router sets a mark in the packet to notify the incipient congestion to the destination node. The destination node receives the marked packet, and delivers the notification in backward packet. Then the source node reduces its current data window and its sending speed to allay or avoid the congestion in the TCI/IP networks. However, ECN mechanisms require significant modifications on both the TCP source and destination to control congestion. Further, ECN mechanisms are oriented to wired networks with very small transmission error, known as Bit Error Rate (BER), since the TCP assumes that the packet loss due to damage is extremely rare and the overwhelming majority of lost packets is due to congestion in the Internet.
For wireless networks, however, TCP assumption is generally falsexe2x80x94most lost packets are due to errors that occur in the transmission of packets over error-prone media such as infrared or radio-frequency links, as opposed to network congestion. When these errors occur, TCP mistakenly assumes that the network is congested and dramatically reduces its transmission of old and new packets. For example, when a packet is lost, TCP may automatically reset its current data window and threshold, then trap in Slow-Start frequently, which may sharply degrade the throughput of connection. Although there are some algorithms to minimize the impact of losses (such as Fast Retransmit, Fast Recovery and Selected Acknowledgment xe2x80x9cSACKxe2x80x9d) from a throughput perspective, TCP is still sensitive to the loss of one or more individual packets and unnecessarily reduces its sending speed (transmission rate). Further, there is no way to distinguish the packet loss due to Bit Error Rate (BER) from loss due to congestion.
In addition, for wireless networks, the speed of wireless links is often much lower than that of wired links. The great difference of bit rates is easy to cause congestion, which would cause large queues in the period of connection and significantly increase the average delay in the network. Furthermore, the congestion would lead to multiple packet loss at the congested node, which would deteriorate the throughput of a connection for a long period.
Accordingly, there is a need for a more efficient ECN mechanism provided to improve the TCP performance in high-speed packet-switched networks, especially wireless or mobile networks with long transfer delay and high Bit Error Rate (BER). A new ECN mechanism is seriously needed to distinguish congestion packets loss from individual packet loss due to Bit Error Rate (BER), to reject coming into Slow-Start when lost packets are due to Bit Error Rate (BER), and to reduce its sending speed upon detection of incipient congestion notification in order to improve the throughput of connection while minimizing the average of queue size.
Accordingly, various embodiments of the present invention are directed to a new and improved Explicit Congestion Notification (ECN) mechanism, and associated method, for wireless and/or mobile network applications to avoid network congestion in a TCP/IP packet-switched network. Such an advanced ECN mechanism may be an algorithm installed or integrated into a host and/or a computer readable medium for use in a host for avoiding network congestion. In addition, such an enhanced ECN algorithm may be installed in the host of a packet-switched network which uses wireless or mobile links.
In accordance with an embodiment of the present invention, a method of avoiding congestion in such a network may comprise the steps of: transmitting, at a source node, data packets to a destination node, via at least an intermediate node; determining, at the intermediate node, if an incipient congestion is encountered, and if the incipient congestion is encountered, setting a Congestion Experienced (CE) flag in each data packet which indicates the incipient congestion to notify the incipient congestion to the destination node; receiving, at the destination node, a CE data packet, setting an Explicit Congestion Notification-Echo (ECN-Echo) flag in a header of an acknowledgment (ACK) packet subsequent to the CE data packet received, and sending an ECN-Echo ACK packet back to the source node to inform that the incipient congestion was encountered in the network on the path from the source node to the destination node; upon receipt of the ECN-Echo ACK packet, reducing, at the source node, a congestion window and a transmission rate (sending speed) to avoid the congestion in the intermediate node, and determining if a packet loss is due to congestion or due to a transmission error, when the incipient congestion is still encountered in the network on the path from the source node to the destination node; if the packet loss is due to congestion, re-transmitting, at the source node, only a lost packet to the destination node, via the intermediate node; and if the packet loss is due to the transmission error, re-transmitting, at the source node, the lost packet to the destination node, via the intermediate node, while increasing a round-trip timeout (RTO) but maintaining the same congestion window.
Specifically, the ECN-Echo ACK packet is transmitted from the destination node back to the source node without delay, and each CE data packet can only invoke a single ECN-Echo ACK packet, and not a series of ECN-Echo ACK packets. The incipient congestion is encountered, when the average of queue size in the intermediate node exceeds a designated threshold. The packet loss is determined due to congestion, if there is an ECN-Echo flag in the prior data window; otherwise, such a packet loss is determined due to the transmission error, if there is no ECN-Echo flag in the prior data window. This way an original sending speed (transmission rate) can be recovered quickly so as to improve the throughput of connection.
In accordance with another embodiment of the present invention, a data network for wireless and/or mobile network applications may comprise a source node for transmitting data packets; a destination node for receiving the data packets from the source node; and at least one intermediate node disposed between the source node and the destination node, for monitoring the average of queue size of incoming data packets from the source node and providing an Explicit Congestion Notification (ECN) to the destination node; wherein the destination node, in response to ECN, sends an ECN-Echo acknowledgment packet back to the source node to inform that congestion was encountered in the network on the path from the source node to the destination node; wherein the source node, in response to the ECN-Echo acknowledgment packet, reduces a congestion window and a transmission rate (sending speed) to avoid the congestion in the intermediate node, and determines if a packet loss is due to congestion or due to a transmission error, when congestion is still encountered in the network; and wherein the source node re-transmits only a lost packet to the destination node, via the intermediate node if the packet loss is due to congestion, and alternatively, re-transmits the lost packet to the destination node, via the intermediate node, while increasing a round-trip timeout (RTO) but maintaining the same congestion window if the packet loss is due to the transmission error in order to improve the throughput of connection.
In accordance with yet another embodiment, the present invention relates to a computer readable medium having an enhanced Explicit Congestion Notification (ECN) algorithm for wireless network applications, when executed by a host system, performs the following: transmitting data packets to a remote system, via an intermediate system which is installed to set a Congestion Experienced (CE) flag in each data packet experiencing congestion; receiving an ECN-Echo ACK packet sent back from to the remote system, in response to reception of a CE data packet, indicating that congestion was encountered on the path to the remote system; upon receipt of the ECN-Echo ACK packet, reducing a congestion window and a transmission rate to avoid the congestion in the intermediate system; determining if a packet loss is due to congestion or due to a transmission error, when congestion is still encountered on the path to the remote system; if the packet loss is due to congestion, re-transmitting only a lost packet to the remote system, via the intermediate system; and if the packet loss is due to the transmission error, re-transmitting the lost packet to the remote system, via the intermediate system, while increasing a round-trip timeout (RTO) but maintaining the same congestion window.
The present invention is more specifically described in the following paragraphs by reference to the drawings attached only by way of example.